%
%  pyPhon
%
%----------------------------------------------------------------------------%
%                    Basic page layout parameters                            %
%----------------------------------------------------------------------------%

\documentclass[11pt]{article}
\usepackage[letterpaper,hmargin=1.25in,vmargin=1.25in]{geometry} 

\usepackage[bottom]{footmisc}


\usepackage{fancyhdr}
\lhead{{\footnotesize{DRAFT}} -- \today}
\chead{}
\rhead{pyPhon}
\lfoot{}
\cfoot{}
\rfoot{\vspace{1ex} \thepage}
\pagestyle{fancy}

\usepackage{setspace}
\singlespacing

\usepackage{enumitem}
\setlist{noitemsep} 

%----------------------------------------------------------------------------%
%                    Title, author, and affiliation                          %
%----------------------------------------------------------------------------%

\title{%
\psset{yunit=9mm}
\begin{pspicture}(10,4)%\psgrid
\rput(5,4.5){\scalebox{3}{\textbf{pyPhon 1.0}}}
\psline[linewidth=5pt](0,6)(10,6)    
\psline[linewidth=5pt](0,3)(10,3)
\rput(5,2){\scalebox{1.1}{\textbf{Part 1: overview and examples}}}
% \rput(5,0.75){\scalebox{0.80}{Max Bane and Jason Riggle}}    
% \rput(5,0.00){\scalebox{0.70}{University of Chicago, 8/2/10}}    
\rput(5,0.5){\LARGE Max Bane and Jason Riggle}    
\rput(5,-.4){\LARGE University of Chicago}
\rput(5,-1.3){\LARGE \today}
\end{pspicture}
}
\author{}
\date{}

%----------------------------------------------------------------------------%
%                    Fonts and encoding                                      %
%----------------------------------------------------------------------------%

\usepackage[dirty,tipa]{ucs}	% Utf-8
\usepackage[utf8x]{inputenc}	% fonts
\usepackage[T1]{fontenc}		% in Tex

\usepackage{tipa}
\usepackage{pifont}


%----------------------------------------------------------------------------%
%                    Graphics and figures                                    %
%----------------------------------------------------------------------------%

\usepackage{wrapfig}
\usepackage{graphicx}
\usepackage{multido}
\usepackage{pstricks}

\psset{gridcolor=green, subgridcolor=white, dimen=middle,
	   linewidth=1pt, subgriddiv=1, gridlabels=4pt, gridwidth=0.2pt}
		
\newpsstyle{final}{linewidth=0.5pt,fillstyle=solid,fillcolor=gray95,%
				   doubleline=true,doublesep=0.8pt,dimen=outer}


%----------------------------------------------------------------------------%
%                    Algorithms and Theorems                                 %
%----------------------------------------------------------------------------%

\usepackage[ruled,noend,linesnumbered]{algorithm2e}

\usepackage[leqno,fleqn]{amsmath}
\usepackage{amsthm}
\usepackage{amssymb} 
\usepackage{stmaryrd}

\newtheoremstyle{dotless}{}{}{\normalfont}{}{\bfseries}{}{ }{}
\theoremstyle{dotless}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}

\newtheoremstyle{dotlessdefn}{}{}{\normalfont}{}{\bfseries}{}{ }{}
\theoremstyle{dotlessdefn}
\newtheorem{defn}[thm]{Definition}

%\newtheoremstyle{dotlessremark}{}{}{}{}{\itshape}{}{ }{}
%\theoremstyle{dotlessremark}
%\newtheorem{ex}[thm]{Example}

%----------------------------------------------------------------------------%
%                    Bibliography                                            %
%----------------------------------------------------------------------------%

\usepackage{natbib} 
\bibpunct[:]{(}{)}{,}{a}{}{,}

%----------------------------------------------------------------------------%
%                    Hyperlinks                                              %
%----------------------------------------------------------------------------%

\usepackage{hyperref}			% Clickable links in pdfs
\hypersetup{colorlinks,			% nice for large docs and 
			breaklinks,			% for links to web pages
            linkcolor=black,
			urlcolor=darkblue,
            anchorcolor=darkblue,
			citecolor=black}

			%----------------------------------------------------------------------------%
%                    Other packages                                          %
%----------------------------------------------------------------------------%

\usepackage{covington}
\usepackage{calc}
\usepackage{ifthen}
			%----------------------------------------------------------------------------%
%                    New Commands                                            %
%----------------------------------------------------------------------------%

\newcommand{\hand}{{\large \ding{43}}}		% OT-Hand
\newcommand{\Con}[1]{{\sc #1}}				% Constraint-name typeface
\newcommand{\M}[1]{$\llbracket${\sc #1}%	% 'FSA-name' typeface
				   $\rrbracket$}

\newcommand{\Adm}[1]{\text{\raisebox{2pt}{$\,\underrightarrow{#1}\,$}}}

%\newcommand{\Or}{\begin{pspicture}(0.25,0)
%		\rput(0.1,0.1){\scalebox{0.58}{$\mathcal{R}$}}
%		\pscircle[linewidth=0.2pt](0.1,0.1){0.125}\end{pspicture}}

\newcommand{\Or}{\ensuremath{\min_\mathcal{R}}}
\newcommand{\Ur}{\ensuremath{\sqcup_\mathcal{R}}}
\newcommand{\Ptr}{\ensuremath{\times_\mathcal{R}}}

\newcommand{\stack}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand{\NIL}{\ensuremath \varnothing}
\newcommand{\NILc}{$\NIL,\{\epsilon\}$}
\newcommand{\INF}{{\scriptsize $\infty$}}
\newcommand{\INFc}{{\scriptsize $\infty$}\hspace{0.5pt},$\;\emptyset$}
\newcommand{\odv}{\begin{pspicture}(0,0)
\rput(-.05,0.19){{\footnotesize $ons,$}}
\rput(0.05,-.18){{\footnotesize $dpv$}}
\end{pspicture}}
\newcommand{\dvc}{\begin{pspicture}(0,0)
\rput(0,0.2){{$dpv,$}}
\rput(0.1,-.2){{$dpc$}}
\end{pspicture}}
\newcommand{\minn}{{\textbf{min}}}
\newcommand{\hopt}{$\mathcal{H}$\Con{-Opt}}
\newcommand{\minr}[2]{\textbf{min}$_{\mathcal{R}}$(#1,#2)}
\newcommand{\Hr}{$\succ_{\mathcal{R}}$}
\newcommand{\con}{{\sc Con}}
\newcommand{\cinf}{$\infty$}
\newcommand{\rd}[1]{\textcolor{red}{\textbf{#1}}}
\newcommand{\bl}[1]{\textcolor{blue}{\textbf{#1}}}
\newcommand{\pur}[1]{\textcolor{purp}{\textbf{#1}}}
\newcommand{\eval}{E{\footnotesize{VAL}}}
\newcommand{\heval}{$\mathcal{H}$-E{\footnotesize{VAL}}}
%\newcommand{\evala}{$\llbracket$E{\footnotesize{VAL}}$_\mathcal{A}\rrbracket$}
\newcommand{\evala}{$\llbracket$E{\footnotesize{VAL}}$\rrbracket$}
\newcommand{\gen}{\ensuremath{Gen}}
\newcommand{\io}{$(input,output)$ }
\newcommand{\D}{{\Large\bf{.}}}
\newcommand{\DOT}{{\Large\bf{.}}}
\newcommand{\depc}{{\sc{DepC}}}
\newcommand{\depv}{{\sc{DepV}}}
\newcommand{\Max}{{\sc{Max}}}
\newcommand{\ons}{{\sc{Onset}}}
\newcommand{\noc}{{\sc{NoCoda}}}
\newcommand{\cln}{\hspace{1pt}:\hspace{1pt}}
\newcommand{\aaa}{$\alpha$$\to$$\alpha$\cln\oset}
\newcommand{\maxa}{\Con{x}$\to$$\varnothing$\cln\{$max$\}}
\newcommand{\depa}{$\varnothing$$\to$\Con{x}\cln\{$dep$\}}
\newcommand{\dep}[1]{$\varnothing$$\to$\Con{#1}\cln%
										 \{$dep$\hspace{0.33pt}-\Con{#1}\}}

%----------------------------------------------------------------------------%
%                    New colors                                              %
%----------------------------------------------------------------------------%

\newrgbcolor{purp}{0.7 0.0 0.7}
\newrgbcolor{ltblue}{0.8 0.9 1.0}
\newrgbcolor{ltgreen}{0.8 1.0 0.85}
\newrgbcolor{ltred}{1.0 0.9 0.8}
\newrgbcolor{red}{0.7 0.0 0.0}
\newrgbcolor{blue}{0.0 0.0 0.7}
\newrgbcolor{darkblue}{0.0 0.0 0.4}
\newrgbcolor{ltelo}{1.0 1.0 0.8}
\newrgbcolor{ltpurple}{1 0.8 1}

\newgray{gray4}{0.4}
\newgray{gray6}{0.6}
\newgray{gray8}{0.8}
\newgray{gray9}{0.9}
\newgray{gray90}{0.9}
\newgray{gray95}{0.95}
\newgray{gray97}{0.97}

%----------------------------------------------------------------------------%
%                    A tableau environment                                   %
%  [#1-1st Col %-width]  #2-n.Constraints   #3-n.Candidates   #4-Col wid/cm  %
%----------------------------------------------------------------------------%
\newcounter{xc}	  \newcounter{x0}
\newcounter{yc}	  \newcounter{y0}	  
\newcounter{zc}   \newcounter{z0}		\newlength{\rowmax} 
\newlength{\col}  \setlength{\col}{1mm}
\newlength{\row}  \setlength{\row}{1.1mm}
\newboolean{ding} \setboolean{ding}{false}

\newenvironment{tableau}[4][2]{%
\bigskip\medskip\refstepcounter{equation}%
\setcounter{xc}{#2-1}   		\setcounter{x0}{#2}
\setcounter{yc}{#3+1}  			\setcounter{y0}{#3}
\setcounter{zc}{10*\real{#1}-5} \setcounter{z0}{10*\real{#1}-5}
\setcounter{enumi}{1}
\psset{xunit=#4mm,yunit=1.5pt,linewidth=0.6pt,framearc=0}
\noindent\begin{pspicture}(0,0)\rput[l](0,#35){(\theequation)}\end{pspicture}%
\hspace*{8.75mm} %<--Tableau inset
\begin{pspicture}(-\arabic{z0},5)(\arabic{x0}5,\arabic{yc}5)%\psgrid
\multido{\ir=#30+-10}{#3}{\rput[l](-\arabic{z0},\ir)%
		{\hspace{2pt}\textit{\alph{enumi}}.\stepcounter{enumi}}}
\setcounter{xc}{#2+1} \setcounter{yc}{#30+10}
\setlength{\rowmax}{\arabic{xc}mm} \setcounter{xc}{0}
\psdot[linecolor=white](0,30)}{ %Begin Code -|- End Code
\setcounter{yc}{\value{y0}+1}
\multido{\nh=05+10}{\arabic{x0}}{\psline[linestyle=dashed,dash=2pt 1pt,%
		linewidth=0.5pt,dimen=middle](\nh,5)(\nh,\arabic{yc}5)}
\multido{\nw=15+10}{\arabic{y0}}{\psline(-\arabic{z0},\nw)(\arabic{x0}5,\nw)}
\psline[linewidth=1.4pt](5,5)(5,\arabic{yc}5)
\psline[linewidth=1.4pt](-\arabic{z0},\arabic{y0}5)(\arabic{x0}5,\arabic{y0}5)
\psline[linecolor=white](5,5)(5,\arabic{yc}5)
\psline[linecolor=white](-\arabic{z0},\arabic{y0}5)(\arabic{x0}5,\arabic{y0}5)
\psframe[linewidth=1pt,framearc=0.025,dimen=middle]%
(-\arabic{z0},5)(\arabic{x0}5,\arabic{yc}5)
\end{pspicture}\par\medskip}

\newcounter{n1}	\newcounter{n2}
\newcommand{\Shade}[5][gray90]{%
			\setcounter{n1}{#2*10-5}\setcounter{n2}{#3*10-5}
			\psframe*[linecolor=#1](\arabic{n1},\arabic{n2})(#45,#55)}

\newcommand{\Wins}[1]{\setcounter{n1}{\value{y0}-#1+1}%
			\setboolean{ding}{true}%
			\rput[l](-\arabic{z0},\arabic{n1}0){~~~\hand}}
			
\newcommand{\Solid}[1]{\setcounter{n1}{\value{y0}+1}
			\psline[linewidth=0.8pt,dimen=middle](#15,5)(#15,\arabic{n1}5)}

\newcommand{\C}[1]{\ifthenelse{\lengthtest{\row=1.1mm}}{%
		   	\rput[l](-\arabic{z0},\arabic{yc}){%
			\ifthenelse{\lengthtest{\col>\row}}{\hspace{5mm}%
			\ifthenelse{\boolean{ding}}{\phantom{\hand}}{}#1}%
			{\hspace*{3mm}#1}}
		   	\addtocounter{xc}{10}\addtolength{\row}{1mm}}{%
		   	\rput(\arabic{xc},\arabic{yc}){%
			\ifthenelse{\lengthtest{\col>\row}}{#1}{\Con{#1}}}
		   	\ifthenelse{\lengthtest{\row<\rowmax}}%
		   	{\addtocounter{xc}{10}\addtolength{\row}{1mm}}%
		   	{\setcounter{xc}{0}\addtocounter{yc}{-10}
		    \addtolength{\col}{10cm}\setlength{\row}{1.1mm}}}}


%----------------------------------------------------------------------------%
%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%
%./\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\.%
%/  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \%
%    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    %
%%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%
%----------------------------------------------------------------------------%
\begin{document}
%----------------------------------------------------------------------------%
%                    Contents page                                           %
%----------------------------------------------------------------------------%
% \thispagestyle{empty}
% \begin{center}
% \begin{pspicture}(0,0)
% \rput(0,1.0){\bf \huge{pyPhon}}
% \rput(0,0.3){Max Bane and Jason Riggle, University of Chicago}
% \rput(0,-0.3){DRAFT -- \today}
% \end{pspicture}
% \end{center}
% \vspace{-6pt}
% \tableofcontents
% \normalsize
%----------------------------------------------------------------------------%
%                    First page                                              %
%----------------------------------------------------------------------------%
\maketitle
\setcounter{page}{1}
\thispagestyle{empty}
% \begin{abstract} \vspace{6pt}
% \hspace{-28pt}\begin{tabular}{p{5.5in}}
% Abstractions.\\
% \end{tabular} 
% \end{abstract}  %-- words


%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%
%./\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\.%
%/  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \%
%    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    %
%./\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\.%
%/  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \%
%    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    %
%%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%

\vspace{2cm}
\begin{figure}[ht] \centering
\psset{framearc=0.1,xunit=12mm,yunit=7mm,dash=3pt 2pt}
\begin{pspicture}(0,-1)(12,5)\psgrid

	\psframe[fillstyle=solid,linewidth=0.5pt,linestyle=dashed,
	fillcolor=ltblue](0.0,3.5)(3.45,4.5)
	\psframe[linewidth=1.5pt](0,2.5)(3.45,4.5)
	\rput[l](0.1,4){\texttt{pyphon\_makemodel}} 
	\rput[l](0.1,3){\emph{input:} \textbf{modelDesc.csv}} 
	
	\psellipse[fillstyle=solid,fillcolor=ltred](2.5,-0.5)(1.0,0.8)
	\rput(2.5,-0.5){\textbf{model.mod}}

	\psframe[fillstyle=solid,linewidth=0.5pt,linestyle=dashed,
	fillcolor=ltblue](3.9,3.5)(7.35,4.5)	
	\psframe[linewidth=1.5pt](3.9,1)(7.35,4.5)
	\rput[l](4.1,4){\texttt{pyphon\_maketableaux}}
	\rput[rB](5,2.8){\emph{input:}} 
	\rput[lB](5.1,2.8){\textbf{model.mod}}
	\rput[l](5.1,2.25){\textbf{inputs.csv}}
	\rput[r](5,1.5){\emph{option:}}
	\rput[l](5.1,1.5){OT/HG}

	\psellipse[fillstyle=solid,fillcolor=ltred](6.5,-0.5)(1.1,0.8)	
	\rput(6.5,-0.5){\textbf{tableaux.csv}}

	\psframe[fillstyle=solid,linewidth=0.5pt,linestyle=dashed,
	fillcolor=ltblue](7.9,3.5)(11.4,4.5)	
	\psframe[linewidth=1.5pt](7.9,1)(11.4,4.5)
	\rput[l](8.1,4){\texttt{pyphon\_generate}}
	\rput[rB](9,2.8){\emph{input:}} 
	\rput[lB](9.1,2.8){\textbf{tableaux.csv}}
	\rput[l](9.1,2.25){\textbf{grammars.csv}}
	\rput[r](9,1.5){\emph{option:}}
	\rput[l](9.1,1.5){which grammar}

	\psellipse[fillstyle=solid,fillcolor=ltred](11,-0.5)(1.1,0.8)	
	\rput(11,-0.5){\textbf{typology.csv}}
	
	\psline[arrowsize=0.2]{->}(2.4,2.5)(2.4,0.4)
	\psline[arrowsize=0.2]{->}(2.6,0.6)(2.4,2.6)
	
\end{pspicture}
\vspace{-6pt}
\caption{{\sc PyPhon} flow chart} \label{fig:pyPhonFlow}
\end{figure}


\onehalfspacing
\section{Introduction}

\paragraph{Monoids} A \emph{monoid} is a triple ($M,\cdot,\bar{1}$) consisting of a set, $M$ a closed associative binary operator $\cdot\,$, and a `neutral' element $\bar{1}$ such that $a\cdot\bar{1}=a$ for all $a\in M$. Two important kinds of monoids are what we will call \emph{words} and \emph{weights}. 
% 
% \paragraph{Words} When the set over which the monoid is stated is finite it is often referred to as an `alphabet' and its elements called `symbols' (or letters). Furthermore, if the binary operator is concatenation the neutral element is usually called `the empty string' and denoted $\epsilon$. This monoid is usually written $(\Sigma, \cdot, \epsilon)$ and, when the intent is clear, it is referred to as $\Sigma$.
% 
% \paragraph{Weights} When the set over which the monoid is stated is not finite it ...
% 
% \paragraph{Kleene Star} This is infinite summation. $\Sigma^*$ is the set of all strings that can be made by concatenating zero or more strings from $\Sigma$ (i.e.~for $\Sigma$ this is the set of all finite strings of symbols in $\Sigma$ including the empty string).
% 
% 
% \paragraph{Morphisms} A \emph{morphism} from one monoid to another preserves... e.g. words to lengths.
% 
% \paragraph{Semirings} dioids, star-semirings, ordered, complete, continuous, conway. 
% 
% \paragraph{Formal Power Series} - is a function from $\Sigma^*$ to a semiring $S$. When such a function can be computed with a finite-state machine it is called a \emph{rational power series}.      
% 
% This package is for implementing rational power series. 
% 
% 
% \section{Components}
% 
% We have three basic kinds of objects: \textbf{algebras}, \textbf{automata}, and \textbf{algorithms}. We should probably keep them as distinct as possible so that we can swap in alternatives cleanly. 
% 
% \subsection{Common Structures (algebra)}
% 
% \paragraph{`words'} Linguistic structures/representations will appear on the arcs in machines and will be referenced by operations in semirings. Some of the things we will want to use are: 
% \begin{itemize}
%   \item symbols and strings
%   \item feature bundles (sets of symbols/strings)
%   \item and maybe regular expressions
% \end{itemize}
% These should be represented by monoids $(\mathbb{X},\cdot,\bar{1})$ where $\mathbb{X}$ is a set, $\cdot$ is a constructor, and $\bar{1}$ is the identity element for the constructor. By convention we could demand that the `*' infix acted like the appropriate constructor. 
% 
% \paragraph{`weights'} These will also be associated with transitions in the automata and operations in the semirings. Some of the ones we will want to use are: 
% \begin{itemize}
%   \item multisets
%   \item vectors of integers
% \end{itemize}
% These are what will get compared/evaluated in grammars with optimization-like behavior. These are also specified by monoids $(\mathbb{X},+,\bar{0})$, but in this case we demand that the monoids are commutative and idempotent. Commutative monoids provide an algebraic preordering ≤, defined by x ≤ y if and only if there exists z such that x + z = y. Commutativity along with idempotency mean that the weights form a semilattice. 
% 
% Both of these should be instances of the \textbf{monoid} class which should  have a method that returns the identity element for the operator and the annihilator element if there is one.  
% 
% 
% \paragraph{Dioids} pyPhon should provide a class for idempotent semirings. (we could expand this to k-closed semirings) These should provide: 
% \begin{itemize}
%   \item oplus for their elements
%   \item otimes for their elements
%   \item methods that return the zero and one elements
%   \item a method that returns a morphism from $S\to S'$
% \end{itemize}
% We can specify some of the properties of feasibility semirings as a special case but we should make it general. If $S$ is idempotent then the \emph{natural order} defined by: 
% 
% $a \leq b $ iff $\exists c$ such that $b\oplus c = a$
% 
% \noindent has all the properties that we want. It is a partial order (transitive, reflexive, antisymmetric) that is also monotonic. We want the morphism to be order preserving (there is a fancy name for this). For our feature based semirings we want: $\{a\},\{b\}\in \wp\mathbb{W}_\mathcal{F}$ if $a\subsetplus b$ then $\{a\} \leq \{b\}$
% 
% \paragraph{Examples} We can implement a few of these to show how they work, identify common structures, and play with different models. 
% \begin{enumerate}
%   \item Feasibility Semirings (for cases where the natural order is partial)
%   \begin{enumerate}
%       \item for ranked constraints
%       \item for weighted constraints
%       \item for probabilistic (weighted) constraints
%       \item for stratified rankings
%       \item for partial rankings
%   \end{enumerate}
%   \item Tropical Semirings (for cases where the natural order is total)
%   \begin{enumerate}
%       \item for total rankings
%       \item for `total' weightings
%   \end{enumerate} 
%   \item Other basic semirings: 
%   \begin{enumerate}
%       \item the boolean ring (for accessibility) in graphs
%       \item the viterbi (+,$\times$) for probability of all paths
%   \end{enumerate}
% \end{enumerate}
% There is an interesting inclusion hierarchy here based on how we specify rankings: \\
% ERCs $\supset$ stratified constraints $\supset$ partially ordered constraints $\supset$ totally ordered constraints 
% 
% \subsection{Automata}
% 
% \paragraph{Finite State} pyPhon should have a general representation for (weighted) finite state acceptors/transducers. In the weighted case a \textbf{dioid} will need to be supplied. 
% \begin{itemize}
%   \item We can characterize lists of candidates as simple automata. 
%   \item We can characterize a \emph{text} (list of input forms) as an input with word boundaries `\#.' If automata have a unique final state contenders of a text \textbf{will compute typology}. 
% \end{itemize}
% 
% \paragraph{Context free} This class should also encompass PDA/CFG's. I am not sure how much these will share, but for the weighted cases they will use the same semirings. 
% 
% \subsection{Algorithms}
% 
% \paragraph{Machine building and manipulation} We might include these in the FSA component, but on the other hand there are probably lots of ways to implement these (or outsource the work to something fast in another language), so it makes sense to dissociate them.
% \begin{enumerate}
%   \item epsilon removal
%   \item reversal 
%   \item complement
%   \item minimization 
%   \item determinization
%   \item regular expression to FSA
%   \item regular expression to constraint 
% \end{enumerate}
% 
% \paragraph{Optimization-like algorithms} We will want to compute single-source shortest paths and all-sources shortest paths for arbitrary semirings over FSA.
% 
% \paragraph{Parsing (??)} We could make chart parsers that use the semirings above so that this stuff would extend to CFGs in a natural way. Any such parser would work transparently over right-linear-grammar representations of the finite-state stuff. 
% 
% 
% 
% \section{Functionality}
% 
% %%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%%-%%%%%%%%
% %./\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\..../\.%
% %/  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \../  \%
% %    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    %
% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%%% %%%%%%
% 
\end{document}
